package com.myc.subjects.slidingwindow;

import com.myc.subjects.utils.MapUtils;

import java.util.*;

/**
 * LeetCode题号：76
 *
 * 最小覆盖子串
 *
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
 *
 * 示例 1：
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 *
 * 示例 2：
 * 输入：s = "a", t = "a"
 * 输出："a"
 *
 * 提示：
 * 1 <= s.length, t.length <= 105
 * s 和 t 由英文字母组成
 *
 * 进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-window-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Zuixiaofugaizichuan {

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        //String s = "a";
        //String t = "aa";
        Zuixiaofugaizichuan zuixiaofugaizichuan = new Zuixiaofugaizichuan();
        System.out.println(zuixiaofugaizichuan.minWindow5(s,t));
    }

    /**
     * 方法一：暴力法
     * 时间复杂度：O(n^3)
     * 枚举所有可能的长度大于等于t的子串，找出包含t所有字符的最短子串。
     * 时间复杂度很高，超出了时间限制
     */
    public String minWindow1(String s, String t) {

        String result = "";//定义结果字符串

        //统计t中字符出现的次数，记录在map中
        Map<Character, Integer> tMap = new HashMap<>();
        for(int i = 0; i < t.length(); i++){
            tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
        }

        //遍历s，枚举所有子串
        for(int i = 0; i < s.length() - t.length() + 1;i++){
            for(int j = i + t.length(); j <= s.length(); j++){//注意这里j <= s.length()因为j是子串的后面一位

                String subString = s.substring(i,j);//截取子串

                //获得子串中字符串中字符出现此时，也记录在map中
                Map<Character, Integer> subStringMap = new HashMap<>();
                for(int k = i; k < j; k++){
                    subStringMap.put(s.charAt(k), subStringMap.getOrDefault(s.charAt(k), 0) + 1);
                }
                MapUtils.showMap(subStringMap);

                //判断子串是否包含t中所有字符
                if(check(subStringMap, tMap) && (result == "" || result.length() > subString.length())) result = subString;
            }
        }

        return result;
    }

    /**
     * 方法二：滑动窗口
     * 时间复杂度：O(n^2)
     * 使用窗口滑动的方式代替暴力枚举，省去了一层循环，但是还是超出了时间限制
     * 在s字符串上定义滑动窗口的左右指针，左右指针中间部分作为子串，当子串包含t中所有字符时，左指针右移。当不满足这个条件时右指针左移
     */
    public String minWindow2(String s, String t) {
        String result = "";

        //定义滑动窗口左右指针的起始位置
        int start = 0;
        int end = t.length();

        Map<Character, Integer> tMap = new HashMap<>();
        for(int i = 0; i < t.length(); i++){
            tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
        }

        while(end <= s.length()){

            Map<Character, Integer> subStringMap = new HashMap<>();
            for(int i = start; i < end; i++){
                subStringMap.put(s.charAt(i), subStringMap.getOrDefault(s.charAt(i), 0) + 1);
            }

            if(check(subStringMap, tMap)){
                if(result == "" || (end - start) < result.length()){
                    result = s.substring(start, end);
                }
                start++;//满足包含关系 左指针右移
            }else end++;//不满足 右指针左移
        }

        return result;
    }

    /**
     * 方法三：滑动窗口优化
     * 时间复杂度：O(n)
     * 在方法二中，我们可以发现，每次找到子串，都会重复统计子串中每个字符出现的次数，如果我们每次都只是修改start位置或是end - 1位置的字符的个数，则又可以省去一层循环
     */
    public String minWindow3(String s, String t) {
        String result = "";

        int start = 0;
        int end = t.length();

        Map<Character, Integer> tMap = new HashMap<>();
        for(int i = 0; i < t.length(); i++){
            tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
        }

        //先在遍历之前初始化一下放置子串中字符出现次数的map-->subStirngMap
        Map<Character, Integer> subStringMap = new HashMap<>();
        for(int i = start; i < end; i++){
            if(end <= s.length() && tMap.containsKey(s.charAt(i))){
                subStringMap.put(s.charAt(i), subStringMap.getOrDefault(s.charAt(i), 0) + 1);
            }
        }

        while(end <= s.length()){
            if(check(subStringMap, tMap)){
                if(result == "" || result.length() > end - start){
                    result = s.substring(start, end);
                }
                if(tMap.containsKey(s.charAt(start))) subStringMap.put(s.charAt(start), subStringMap.get(s.charAt(start)) - 1);//subStirngMap中使子串最左侧字符的值-1
                start++;
            }else{
                if(end != s.length() && tMap.containsKey(s.charAt(end))) subStringMap.put(s.charAt(end), subStringMap.getOrDefault(s.charAt(end), 0) + 1);//subStirngMap中使子串最右侧字符的值+1
                end++;
            }
        }
        return result;
    }

    /**
     * 方法四：滑动窗口优化
     * 时间复杂度：O(n)
     * 在方法三的基础上，我们其实可以在遍历的时候一边遍历，一边组建subStringMap，这样就可以省去初始化，使代码更加简洁。
     * 将方法三中的一个循环控制两个指针，改为两个循环分别控制左右指针。
     */
    public String minWindow4(String s, String t) {
        String result = "";

        int start = 0;
        int end = 0;//这里end从0开始遍历

        Map<Character, Integer> tMap = new HashMap<>();
        for(int i = 0; i < t.length(); i++){
            tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
        }

        Map<Character, Integer> subStringMap = new HashMap<>();

        while(end <= s.length()){
            while(check(subStringMap, tMap)){//这里if改为while，里层循环仅控制start指针右移,这个真是非常巧妙
                if(result == "" || result.length() > end - start){
                    result = s.substring(start, end);
                }
                if(tMap.containsKey(s.charAt(start))) subStringMap.put(s.charAt(start), subStringMap.get(s.charAt(start)) - 1);
                start++;
            }

            //外层循环仅控制end指针右移
            if(end != s.length() && tMap.containsKey(s.charAt(end))) subStringMap.put(s.charAt(end), subStringMap.getOrDefault(s.charAt(end), 0) + 1);//subStirngMap中使子串最右侧字符的值+1
            end++;
        }
        return result;
    }

    /**
     * 方法五：滑动窗口再优化
     * 时间复杂度：O(n)
     * 由以上优化可知，我们将subStringMap的变化改为了每次增加一个或减少一个。那么我们在比较子串是否覆盖t时，也可以进行优化
     * 定义一个整型变量，用于保存子串中的字符对于覆盖t是否有贡献的统计值
     * end右移时，end处字符有贡献的话，该值+1；start右移时，start处字符有贡献的话，该值-1
     * 在比较子串是否覆盖t时，我们只要比较贡献值大于等于t长度，则确定覆盖
     * 这样优化就省去了每次遍历t判断是否覆盖的 check() 方法
     */
    public String minWindow5(String s, String t){
        String result = "";

        int start = 0;
        int end = 1;//end从1开始 我们判断的时候用 end-1 处的字符判断
        int contribution = 0;//定义贡献值 用于判断是否覆盖
        Map<Character, Integer> tMap = new HashMap<>();
        for(int i = 0; i < t.length(); i++){
            tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
        }

        Map<Character, Integer> subStringMap = new HashMap<>();

        while(end <= s.length()){

            if(tMap.containsKey(s.charAt(end - 1)) ){
                //如果subStringMap中的统计数量小于tMap中得统计数量，贡献值++
                if(subStringMap.getOrDefault(s.charAt(end - 1), 0) < tMap.get(s.charAt(end - 1))) contribution++;
                subStringMap.put(s.charAt(end - 1), subStringMap.getOrDefault(s.charAt(end - 1),0) + 1);
            }
            //这里只需要比较贡献值与t字符串的长度是否相等即可
            while(contribution == t.length()){
                if(result == "" || result.length() > end - start){
                    result = s.substring(start, end);
                }
                if(tMap.containsKey(s.charAt(start))){
                    //如果subStringMap中的统计数量 小于等于 tMap中得统计数量，贡献值--
                    if(subStringMap.get(s.charAt(start)) <= tMap.get(s.charAt(start))) contribution--;
                    subStringMap.put(s.charAt(start), subStringMap.get(s.charAt(start)) - 1);
                }
                start++;
            }

            end++;
        }
        return result;
    }

    //该方法用于检查t中所有字符是不是在子串中都有，要按数量来确认
    public boolean check(Map<Character,Integer> subStringMap, Map<Character,Integer> tMap){
        for(Character tchar : tMap.keySet()){
            if(tMap.get(tchar) > subStringMap.getOrDefault(tchar, 0)) return false;
        }
        return true;
    }

    //官方题解：滑动窗口
    Map<Character, Integer> ori = new HashMap<Character, Integer>();
    Map<Character, Integer> cnt = new HashMap<Character, Integer>();

    public String minWindowOfficial(String s, String t) {
        int tLen = t.length();
        for (int i = 0; i < tLen; i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0) + 1);
        }
        int l = 0, r = -1;
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        int sLen = s.length();
        while (r < sLen) {
            ++r;
            if (r < sLen && ori.containsKey(s.charAt(r))) {
                cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
            }
            while (checkOfficial() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }
                if (ori.containsKey(s.charAt(l))) {
                    cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                }
                ++l;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

    public boolean checkOfficial() {
        Iterator iter = ori.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            Character key = (Character) entry.getKey();
            Integer val = (Integer) entry.getValue();
            if (cnt.getOrDefault(key, 0) < val) {
                return false;
            }
        }
        return true;
    }
}

/**
 * 总结：
 * 1.善用滑动窗口解决连续子串、连续子数组问题，滑动窗口就是左右指针向同一个方向滑动，形成一个子区间，这样可以将原本需要两层遍历的方式改为了两次遍历。
 * 2.善于利用两个里外两个while分别控制左右指针。
 */
